package com.cxt.utils;

import java.util.ArrayList;
import java.util.List;

public class CleanTspUtil {
    private Integer INF = Integer.MAX_VALUE;
    private Integer N ;
    private Integer M;// = 1 << (N - 1)
    // 存储城市之间的距离
    private Integer[][] g = null;
    // 保存顶点i到状态s最后回到起始点的最小距离
    private Integer[][] dp;// = new Integer[N][M];
    // 保存路径
    List<Integer> path = new ArrayList<>();
    public CleanTspUtil(Integer size) {
        this.N = size;
        this.M = 1 << (N - 1);
        this.dp = new Integer[N][M];
    }
    public void setG(Integer[][] g){
        this.g = g;
    }
    // 核心函数，求出动态规划dp数组
    private void TSP() {
        // 初始化dp[i][0]
        for (int i = 0; i < N; i++) {
            dp[i][0] = g[i][0];
        }
        // 求解dp[i][j],先更新列再更新行
        for (int j = 1; j < M; j++) {
            for (int i = 0; i < N; i++) {
                dp[i][j] = INF;
                // 如果集和j(或状态j)中包含结点i,则不符合条件退出
                if (((j >> (i - 1)) & 1) == 1) {
                    continue;
                }
                for (int k = 1; k < N; k++) {
                    if (((j >> (k - 1)) & 1) == 0) {
                        continue;
                    }
                    if (dp[i][j] > g[i][k] + dp[k][j ^ (1 << (k - 1))]) {
                        dp[i][j] = g[i][k] + dp[k][j ^ (1 << (k - 1))];
                    }
                }
            }
        }
//        for(int i=0;i<N;i++){
//            for(int j=0;j<M;j++){
//                System.out.print("dp("+i+","+Integer.toBinaryString(j)+")"+dp[i][j]+" ");
//            }
//            System.out.println("");
//        }
    }

    // 判断结点是否都以访问,不包括0号结点
    private boolean isVisited(boolean[] visited) {
        for (int i = 1; i < N; i++) {
            if (!visited[i]) {
                return false;
            }
        }
        return true;
    }

    // 获取最优路径，保存在path中,根据动态规划公式反向找出最短路径结点
    private void getPath() {
        // 标记访问数组
        boolean[] visited = new boolean[N];
        // 前驱节点编号
        int pioneer = 0;
        double min = INF;
        int S = M - 1;
        int temp=10;
        // 把起点结点编号加入容器
        path.add(0);

        while (!isVisited(visited)) {
            for (int i = 1; i < N; i++) {//从i号城市回到0号（起点）城市
                if (!visited[i] && (S & (1 << (i - 1))) != 0) {//i号城市不在已访问城市中
                    //如果当前结点到前驱结点的距离加上0->S->i->0的距离小于min
                    if (min > g[i][pioneer] + dp[i][(S ^ (1 << (i - 1)))]){//
                        min = g[i][pioneer] + dp[i][(S ^ (1 << (i - 1)))];
                        temp = i;
                    }
                }
            }
            //第一遍循环找出去某个城市再回来的最短路径
            //第二遍
            pioneer = temp;//上一个城市
            path.add(pioneer);//添加到路径中
            visited[pioneer] = true;//标记为已访问
            S = S ^ (1 << (pioneer - 1));//更新S
            min = INF;//重置min
        }
    }

    // 输出路径
    private void printPath() {
        System.out.print("最小路径为：");
        for (int i = 0; i < path.size(); i++) {
            System.out.print(path.get(i));
            if (i != path.size() - 1) {
                System.out.print("--->");
            }
        }
        // 单独输出起点编号
        System.out.print(0);
    }
    // 获取最短路径
    public List<Integer> getTSPPath() {
        if (g == null) {
            System.out.println("请先初始化g[][]数组");
            return null;
        }
        this.TSP();
        this.getPath();
        return path;
    }
}
